from typing import List


class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间[left, right]
        while left <= right:
            # nums[left - 1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1 # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1 # 范围缩小到 [mid+1, right]
        # left = right + 1
        # nums[left] = nums[rigght+1]>=target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    
    def lower_bound1(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 左闭右开区间[left, right)
        while left < right:
            # nums[left - 1] < target
            # nums[right] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid # 范围缩小到 [left, mid)
            else:
                left = mid + 1 # 范围缩小到 [mid+1, right)
        # 循环结束后 left = right
        # 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left
    
    def lower_bound2(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 开区间(left, right)
        while left + 1 < right:
            # nums[left] < target
            # nums[right] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid # 范围缩小到 (left, mid)
            else:
                left = mid # 范围缩小到 (mid+1, right)
        # 循环结束后 left +1 = right
        # 此时 nums[left] < target 而 nums[right] >= target
        # 所以 right 就是第一个 >= target 的元素下标
        return right
    
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = self.lower_bound(nums, target + 1) -1
        return [start, end]
        